// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// Longest函数计算两个输入字符串的最长公共子序列（LCS）的长度
// str1 和 str2。
// 它使用动态规划用表示长度的值填充二维切片（制表符）
// str1 和 str2 的每对前缀的 LCS。
// 函数返回tab[len1][len2]的值，其中len1和len2分别是str1和str2的长度，
// 分别。
func Longest(str1, str2 string) int {
	// 获取输入字符串的长度
	len1 := len(str1)
	len2 := len(str2)

	// 创建一个大小为 (len1+1) x (len2+1) 的二维切片来存储 LCS 长度
	tab := make([][]int, len1+1)
	for i := range tab {
		tab[i] = make([]int, len2+1)
	}

	// 使用动态规划填充选项卡切片
	for i := 0; i <= len1; i++ {
		for j := 0; j <= len2; j++ {
			if i == 0 || j == 0 {
				// 基本情况：空字符串和任意字符串的 LCS 为 0
				tab[i][j] = 0
			} else if str1[i-1] == str2[j-1] {
				// str1 和 str2 最后一个字符匹配时的情况
				// 将前缀 str1[0:i-1] 和 str2[0:j-1] 的 LCS 长度加 1
				tab[i][j] = tab[i-1][j-1] + 1
				if i < len1 {
					fmt.Printf("%c", str1[i])
					// 移动到 str1 和 str2 中的下一个字符
					i++
					j++
				}
			} else {
				// 当 str1 和 str2 的最后一个字符不匹配时的情况
				// 取前缀 str1[0:i-1] 和 str2[0:j] 的最大 LCS 长度和
				// 前缀 str1[0:i] 和 str2[0:j-1] 的 LCS 长度
				tab[i][j] = max(tab[i-1][j], tab[i][j-1])
			}
		}
	}
	fmt.Println()
	// 返回整个字符串 str1 和 str2 的 LCS 长度
	return tab[len1][len2]
}

// Function max takes a variable number of integers and returns the maximum value among them.
func max(more ...int) int {
	maxNum := more[0]
	for _, elem := range more {
		if maxNum < elem {
			maxNum = elem
		}
	}
	return maxNum
}

func main() {
	str1 := "TABTABTAB"
	str2 := "ATABTABTAB"
	fmt.Println(Longest(str1, str2))
}

//$ go run LCS.go
//ABTBTA
//1
